package com.dap.utils;

import com.google.common.collect.Lists;
import org.springframework.util.StringUtils;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * 将 不连续的范围 拼接 为 连续的
 */
public class ContinuousRange {
    // 二分查找比key小的最大值 的位置
    private static <T> int indexedBinarySearchLower(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0) {
                low = mid + 1;

                if (low > high)
                    return mid;
            } else if (cmp > 0) {
                high = mid - 1;

                if (low > high)
                    return mid-1;
            } else {
                return mid; // key found
            }
        }
        return -(low + 1);  // key not found
    }


    public static class RangeBlock implements Comparable<RangeBlock> {
        public BigDecimal home;
        public BigDecimal end;

        public RangeBlock() {}
        public RangeBlock(BigDecimal home, BigDecimal end) {
            this.home = home;
            this.end = end;
        }

        @Override
        public String toString() {
            return "home="+home.toString() + ", end="+end.toString();
        }

        @Override
        public int compareTo(RangeBlock o) {
            return this.home.compareTo(o.home);
        }

        /**
         * sectionStr 为范围字符串, 例如下面三种类型
         * 12.4-43.3
         * -5.3
         * 23.3-
         *
         * 根据范围字符串生成范围对象
         * 如果最小值没有, 则使用 defaultMin
         * 如果最大值没有, 则使用 defaultMax
         * 如果字符串为空, 则返回null
         * 如果字符串为-, 返回[defaultMin, defaultMax]
         * */
        public static RangeBlock generateByStr(String sectionStr, char separator, BigDecimal defaultMin, BigDecimal defaultMax) {
            RangeBlock section = new RangeBlock(defaultMin, defaultMax);

            if (StringUtils.isEmpty(sectionStr))
                return null;

            int separatorIdx = sectionStr.indexOf(separator);
            if (separatorIdx < 0) {
                section.home = new BigDecimal(sectionStr);
                return section;
            }

            if (separatorIdx > 0) {
                section.home = new BigDecimal(sectionStr.substring(0, separatorIdx));
            }

            if (separatorIdx+1 < sectionStr.length()) {
                section.end = new BigDecimal(sectionStr.substring(separatorIdx+1));
            }

            return section;
        }
    }

    private final List<RangeBlock> l = Lists.newArrayList();

    public void addBlock(BigDecimal home, BigDecimal end) {
        assert(home.compareTo(end) <= 0);

        int lower = indexedBinarySearchLower(l, new RangeBlock(home,end));
        if (lower < 0)
            lower = 0;

        int size = l.size();
        for (int i=lower; i<size; ++i) {
            RangeBlock ab = l.get(i);
            boolean mergeRest = false;
            if (ab.home.compareTo(home) <= 0 && end.compareTo(ab.end) <= 0) {
                return;
            } else if (home.compareTo(ab.home) <= 0 && ab.home.compareTo(end) <= 0) {
                ab.home = home;

                if (ab.end.compareTo(end) >= 0) {
                    return;
                } else {
                    ab.end = end;
                    mergeRest = true;
                }
            } else if (home.compareTo(ab.end) <= 0 && ab.end.compareTo(end) <= 0) {
                ab.end = end;
                mergeRest = true;
            }

            // 与后面的合并
            if (mergeRest) {
                ++i;
                while (i < l.size()) {
                    RangeBlock ab2 = l.get(i);
                    if (end.compareTo(ab2.home) < 0)
                        return;
                    if (end.compareTo(ab2.end) <= 0) {
                        ab.end = ab2.end;
                        l.remove(i);
                        return;
                    } else {
                        l.remove(i);
                    }
                }
                return;
            }

            if (end.compareTo(ab.home) < 0) {
                l.add(i, new RangeBlock(home, end));
                return;
            }
        }

        l.add(new RangeBlock(home, end));
    }

    /**
     * 判断home,end表示的范围是否完全包含在当前的范围中
     * */
    public boolean isWithin(RangeBlock rb) {
        BigDecimal home = rb.home;
        BigDecimal end = rb.end;

        int lower = indexedBinarySearchLower(l, rb);
        if (lower < 0)
            lower = 0;

        int size = l.size();
        for (int i=lower; i<size; ++i) {
            RangeBlock ab = l.get(i);
            if (ab.home.compareTo(home) <= 0 && end.compareTo(ab.end) <= 0) {
                return true;
            } else if (home.compareTo(ab.home) < 0) {
                return false;
            }
        }

        return false;
    }

    // 判断是否为other的父集
    public boolean isParent(ContinuousRange other) {
        for (RangeBlock rb : other.l) {
            if (!this.isWithin(rb)) {
                return false;
            }
        }
        return true;
    }

    // 判断是否有重合区间, 所有区间为[,)形式, 如 [0,10)
    public boolean hasPolymerizationSectionCloseOpen(final RangeBlock rangeBlock) {
        if (rangeBlock.home.equals(rangeBlock.end)) {
            for (RangeBlock b : l) {
                if (b.home.equals(b.end)) {
                    if (b.home.compareTo(rangeBlock.home) == 0)
                        return true;
                } else {
                    if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) < 0)
                        return true;
                }
            }
        } else {
            for (RangeBlock b : l) {
                if (b.home.equals(b.end)) {
                    if (rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) < 0)
                        return true;
                } else {
                    if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) < 0
                            || b.home.compareTo(rangeBlock.end) < 0 && rangeBlock.end.compareTo(b.end) <= 0
                            || rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) < 0
                            || rangeBlock.home.compareTo(b.end) < 0 && b.end.compareTo(rangeBlock.end) <= 0)
                        return true;
                }
            }
        }
        return false;
    }
    // 获取所有重合区间, 所有区间为[,)形式, 如 [0,10)
    public List<RangeBlock> getAllPolymerizationSectionsCloseOpen(final RangeBlock rangeBlock) {
        List<RangeBlock> result = new ArrayList<>();
        if (rangeBlock.home.equals(rangeBlock.end)) {
            for (RangeBlock b : l) {
                if (b.home.equals(b.end)) {
                    if (b.home.compareTo(rangeBlock.home) == 0)
                        result.add(b);
                } else {
                    if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) < 0)
                        result.add(b);
                }
            }
        } else {
            for (RangeBlock b : l) {
                if (b.home.equals(b.end)) {
                    if (rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) < 0)
                        result.add(b);
                } else {
                    if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) < 0
                            || b.home.compareTo(rangeBlock.end) < 0 && rangeBlock.end.compareTo(b.end) <= 0
                            || rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) < 0
                            || rangeBlock.home.compareTo(b.end) < 0 && b.end.compareTo(rangeBlock.end) <= 0)
                        result.add(b);
                }
            }
        }
        return result;
    }

    // 判断是否有重合区间, 所有区间为[,]形式, 如 [0,10]
    public boolean hasPolymerizationSectionCloseClose(final RangeBlock rangeBlock) {
        if (rangeBlock.home.equals(rangeBlock.end)) {
            for (RangeBlock b : l) {
                if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) <= 0)
                    return true;
            }
        } else {
            for (RangeBlock b : l) {
                if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) <= 0
                        || b.home.compareTo(rangeBlock.end) <= 0 && rangeBlock.end.compareTo(b.end) <= 0
                        || rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) <= 0
                        || rangeBlock.home.compareTo(b.end) <= 0 && b.end.compareTo(rangeBlock.end) <= 0)
                    return true;
            }
        }
        return false;
    }
    // 获取所有重合区间, 所有区间为[,]形式, 如 [0,10]
    public List<RangeBlock> getAllPolymerizationSectionsCloseClose(final RangeBlock rangeBlock) {
        List<RangeBlock> result = new ArrayList<>();
        if (rangeBlock.home.equals(rangeBlock.end)) {
            for (RangeBlock b : l) {
                if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) <= 0)
                    result.add(b);
            }
        } else {
            for (RangeBlock b : l) {
                if (b.home.compareTo(rangeBlock.home) <= 0 && rangeBlock.home.compareTo(b.end) <= 0
                        || b.home.compareTo(rangeBlock.end) <= 0 && rangeBlock.end.compareTo(b.end) <= 0
                        || rangeBlock.home.compareTo(b.home) <= 0 && b.home.compareTo(rangeBlock.end) <= 0
                        || rangeBlock.home.compareTo(b.end) <= 0 && b.end.compareTo(rangeBlock.end) <= 0)
                    result.add(b);
            }
        }
        return result;
    }


    /**
     * 根据数据的起始地址获取该数据所在数据块的索引
     * @return 返回正数代表找到, -1代表未找到
     * */
    public int getBlockIndexByStartAddressCloseOpen(BigDecimal address) {
        int lower = indexedBinarySearchLower(l, new RangeBlock(address, address));
        if (lower < 0)
            lower = 0;

        int size = l.size();
        for (int i=lower; i<size; ++i) {
            RangeBlock ab = l.get(i);
            if (ab.home.compareTo(address) <= 0 && address.compareTo(ab.end) < 0)
                return i;
            if (address.compareTo(ab.home) < 0)
                break;
        }
        return -1;
    }
    public int getBlockIndexByStartAddressCloseClose(BigDecimal address) {
        int lower = indexedBinarySearchLower(l, new RangeBlock(address, address));
        if (lower < 0)
            lower = 0;

        int size = l.size();
        for (int i=lower; i<size; ++i) {
            RangeBlock ab = l.get(i);
            if (ab.home.compareTo(address) <= 0 && address.compareTo(ab.end) <= 0)
                return i;
            if (address.compareTo(ab.home) < 0)
                break;
        }
        return -1;
    }

    public List<RangeBlock> getBlocks() {return l;}
    public RangeBlock getBlock(int index) {return l.get(index);}
    public int getBlockCount() {return l.size();}



    public static ContinuousRange generateRangeByStr(Collection<String> sectionStrs, char separator, BigDecimal defaultMin, BigDecimal defaultMax) {
        ContinuousRange cr = new ContinuousRange();
        for (String sectionStr : sectionStrs) {
            RangeBlock priceSection = RangeBlock.generateByStr(sectionStr, separator, defaultMin, defaultMax);
            if (null != priceSection) {
                cr.addBlock(priceSection.home, priceSection.end);
            }
        }

        return cr;
    }


    public static void main(String[] argv) {
        ContinuousRange cab = new ContinuousRange();
        cab.addBlock(new BigDecimal(0), new BigDecimal(4)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
        cab.addBlock(new BigDecimal(4), new BigDecimal(8)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
        cab.addBlock(new BigDecimal(16), new BigDecimal(20)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
        cab.addBlock(new BigDecimal(24), new BigDecimal(28)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
        cab.addBlock(new BigDecimal(30), new BigDecimal(34)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");

        cab.addBlock(new BigDecimal(0), new BigDecimal(4)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
        cab.addBlock(new BigDecimal(0), new BigDecimal(8)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");

        // 测试过 (0,7~35) (4,7~35) (8,9~35) (12,13~35) (16,17~35) (18,19~35)
        cab.addBlock(new BigDecimal(12), new BigDecimal(15)); for (RangeBlock ab : cab.getBlocks()) {System.out.print(ab.home + "-" + ab.end + " ");} System.out.println("");
    }
}
